package com.myself.module.source.sort;

import java.util.Arrays;

/**
 * @author 瑟瑟发抖
 * @version 1.0
 * @description 快排
 * @date 2024/4/12 18:00
 */

public class QuickSort {

    private static int[] ints;

    public static void sort(int[] input) {
        ints = new int[input.length];
        sort(input, 0, input.length - 1);
    }

    public static void sort(int[] input, int smallIndex, int bigIndex) {
        if (bigIndex <= smallIndex) {
            return;
        }
        int partition = partition(input, smallIndex, bigIndex);
        sort(input, smallIndex, partition - 1);//左
        sort(input, partition + 1, bigIndex);//右


    }

    public static int partition(int[] a, int low, int high) {

        int i = low, j = high + 1;
        //将原数组复制到临时数组中
        int element = a[i];
        while (true) {
            //左比指定元素小
            //右比指定元素大
            while (a[++i] < element) if (i == high) break;
            while (a[--j] > element) if (j == low) break;
            if (i >= j) break;
            int middleInt = a[i];
            a[i] = a[j];
            a[j] = middleInt;
        }
        int middleInt = a[j];
        a[j] = element;
        a[low] = middleInt;

        return j;
    }


    public static void main(String[] args) {
        int[] ints = {1, 8, 9, 5, 4, 100, 11, 12};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
